public class BackPackSolutions {
    /**
     * easy 70. 爬楼梯
     */
    public int climbStairs(int n) {
        // 背包大小为n，物品为1和2，完全背包问题
        // 顺序相关下，可重复使用物品，求填满背包的方法
        // 先遍历背包大小，再遍历物品
        int[] dp = new int[n + 1];
        dp[0] = 1;
        // 遍历背包容量
        for (int i = 1; i <= n; i++) {
            // 遍历物品
            if (i >= 1)
                dp[i] += dp[i - 1];
            if (i >= 2)
                dp[i] += dp[i - 2];
        }
        return dp[n];
    }

    /**
     * mid 322. 零钱兑换
     */
    public int coinChange(int[] coins, int amount) {
        // 背包大小为amount，背包物品为coins，完全背包问题
        // 可重复选凑到一个值，类似爬楼梯
        // 爬楼梯求有多少种方式（顺序相关），零钱兑换求凑成的最少物品数量（顺序无关）
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int coin : coins) {
                if (coin <= i && dp[i - coin] != Integer.MAX_VALUE)
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}
